#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef int ElementType;

typedef struct STable
{
    ElementType *elem;
    int len;
} STable;

void InitSTable(STable &table, int len)
{
    table.elem = (ElementType *)malloc(sizeof(ElementType) * len);
    table.len = len;
    srand(time(NULL));
    for (int i = 0; i < len; i++)
    {
        table.elem[i] = rand() % 100;
    }
}

void PrintSTable(STable table)
{
    for (int i = 0; i < table.len; i++)
    {
        printf("%3d", table.elem[i]);
    }
    printf("\n");
}

void Swap(ElementType &a, ElementType &b)
{
    ElementType tmp = a;
    a = b;
    b = tmp;
}

/*堆排辅助函数*/
void HeapSortHelp(ElementType elem[], int root_index, int len)
{
    int dad = root_index;
    int son = 2 * dad + 1;
    while (son < len)
    {
        if (son + 1 < len && elem[son + 1] > elem[son])
        {
            son++;
        }
        if (elem[dad] < elem[son])
        {
            Swap(elem[dad], elem[son]);
            dad = son;
            son = 2 * dad + 1;
        }
        else
        {
            break;
        }
    }
}

/*堆排序*/
bool HeapSort(ElementType elem[], int len)
{
    for (int i = len / 2 - 1; i >= 0; i--)
    {
        HeapSortHelp(elem, i, len); // 从下至上构建大顶堆
    }
    for (int i = len - 1; i > 0; i--)
    {
        Swap(elem[i], elem[0]);   // 交换堆顶元素
        HeapSortHelp(elem, 0, i); // 构建大顶堆
    }
    return true;
}

void MergeSortHelp(ElementType elem[], int left, int mid, int right)
{
    int left_index = left, right_index = mid + 1, index = left;
    ElementType new_elem[right + 1];
    for (int i = left; i <= right; i++)
    {
        new_elem[i] = elem[i];
    }
    while (left_index <= mid && right_index <= right)
    {
        if (new_elem[left_index] < new_elem[right_index])
        {
            elem[index++] = new_elem[left_index++];
        }
        else
        {
            elem[index++] = new_elem[right_index++];
        }
    }
    while (left_index <= mid)
    {
        elem[index++] = new_elem[left_index++];
    }
    while (right_index <= right)
    {
        elem[index++] = new_elem[right_index++];
    }
}

bool MergeSort(ElementType elem[], int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        MergeSort(elem, left, mid);
        MergeSort(elem, mid + 1, right);
        MergeSortHelp(elem, left, mid, right); // 合并两个有序数组
    }
    return true;
}

int QuickSortHelp(ElementType elem[], int left, int right)
{
    ElementType flag = elem[left];
    while (left < right)
    {
        while (left < right && elem[right] >= flag)
        {
            right--;
        }
        elem[left] = elem[right];
        while (left < right && elem[left] <= flag)
        {
            left++;
        }
        elem[right] = elem[left];
    }
    elem[left] = flag;
    return left;
}

bool QuickSort(ElementType elem[], int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = QuickSortHelp(elem, left, right);
        QuickSort(elem, left, mid - 1);
        QuickSort(elem, mid + 1, right);
    }
    return true;
}

bool BubbleSort(ElementType elem[], int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - 1 - i; j++)
        {
            if (elem[j] > elem[j + 1])
            {
                Swap(elem[j], elem[j + 1]);
            }
        }
    }
    return true;
}

bool InsertSort(ElementType elem[], int len)
{
    ElementType flag;
    int j;
    for (int i = 1; i < len; i++)
    {
        flag = elem[i];
        for (j = i - 1; j >= 0 && elem[j] > flag; j--)
        {
            elem[j + 1] = elem[j];
        }
        elem[j + 1] = flag;
    }
    return true;
}

bool SelectSort(ElementType elem[], int len)
{
    int min_index;
    for (int i = 0; i < len - 1; i++)
    {
        min_index = i;
        for (int j = i + 1; j < len; j++)
        {
            if (elem[j] < elem[min_index])
            {
                min_index = j;
            }
        }
        Swap(elem[i], elem[min_index]);
    }
    return true;
}

int main()
{
    STable table;
    InitSTable(table, 15);
    ElementType *new_elem;
    memcpy(new_elem, table.elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    printf("-----------------HeapSort------------------------\n");
    HeapSort(table.elem, table.len);
    PrintSTable(table);
    memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    printf("-----------------MergeSort------------------------\n");
    MergeSort(table.elem, 0, table.len - 1);
    PrintSTable(table);
    memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    printf("-----------------QuickSort------------------------\n");
    QuickSort(table.elem, 0, table.len - 1);
    PrintSTable(table);
    memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    // printf("-----------------BubbleSort------------------------\n");
    // BubbleSort(table.elem, table.len);
    // PrintSTable(table);
    // memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    // PrintSTable(table);
    printf("-----------------InsertSort------------------------\n");
    InsertSort(table.elem, table.len);
    PrintSTable(table);
    memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    printf("-----------------SelectSort------------------------\n");
    SelectSort(table.elem, table.len);
    PrintSTable(table);
    return 0;
}